﻿

using System.Collections.Generic;

namespace Graph.Algorithm.Core
{
    /// <summary>
    /// 
    /// </summary>
    public class KruskalService
    {
        private List<GraphEdge> _treeEdges = new List<GraphEdge>();

        public IList<GraphEdge> RunAlgm(IEnumerable<GraphEdge> edges)
        {
            edges = edges
                .Where(e => e.weight != 0)
                .OrderBy(e => e.weight);
             
            List<GraphEdge> treeEdges = new List<GraphEdge>();
            List<HashSet<int>> treeSets = new List<HashSet<int>>();//并查集采用hashset结构构造
            edges.Select(e => e.stVertexId).Distinct().ToList()
                .ForEach(id => treeSets.Add(new HashSet<int>() { id }));
             
            foreach (var edge in edges)
            {
                if (treeSets.Count() == 1) break;
                int stIndex = edge.stVertexId;
                int edIndex = edge.edVertexId;

                //边的两侧是否同树
                bool isInSameTree = treeSets.Any(t => t.Contains(stIndex) && t.Contains(edIndex));
                //当前边集合T是否有该边 
                bool isAdded = treeEdges.Contains(edge);
                //综合判断
                bool canAdd = !isInSameTree && !isAdded;

                if (canAdd)
                {
                    treeEdges.Add(edge);//add

                    var stTree = treeSets.Where(t => t.Contains(stIndex)).First();
                    var edTree = treeSets.Where(t => t.Contains(edIndex)).First();

                    stTree.UnionWith(edTree);
                    treeSets.Remove(edTree);
                }
            }
            _treeEdges = treeEdges;
            return treeEdges;

        }

        public IList<TreeNode> GetTreeEntity()
        {
            List<TreeNode> treeNodes = new List<TreeNode>();
            List<GraphEdge> treeEdges = _treeEdges;

            foreach (var group in treeEdges.GroupBy(t => t.stVertexId))
            {
                TreeNode node = new TreeNode();
                node.id = group.First().id;
                node.childIds.AddRange(group.Select(g => g.edVertexId));
                treeNodes.Add(node);
            }

            return treeNodes;
        }

        public struct TreeNode
        {
            public TreeNode()
            {
                this.id = 0;
                this.childIds = new List<int>();
            }

            public int id { get; set; }
            public List<int> childIds { get; set; }
        } 
    }


}
